package com.duoduo.sort;

import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @description: 数据流中的中位数
 * @author: chaidl  ！
 * @create: 2022-03-10 21:10
 */
public class 数据流中的中位数 {
    /**
     * initialize your data structure here.
     * // 大顶堆存储较小一半的值
     */
    PriorityQueue<Integer> min, max;

    public 数据流中的中位数() {
        min = new PriorityQueue<Integer>();
        max = new PriorityQueue<Integer>((a, b) -> (b - a));
    }

    public void addNum(int num) {
    //    一个小顶堆，一个大顶堆
    //     长度为奇数时先放入小顶堆,重新排序后在插入到大顶堆
        if (min.size()!=max.size()){
            min.offer(num);
            max.offer(min.poll());
        }else {
            max.offer(num);
            min.offer(max.poll());
        }
    }

    public double findMedian() {
        if (min.size() != max.size()){
            return min.peek();
        }else {
            return Double.valueOf(min.peek()+max.peek())/2;
        }
    }
}
